//给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 
//
// 设计一个算法使得这 m 个子数组各自和的最大值最小。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [7,2,5,10,8], m = 2
//输出：18
//解释：
//一共有四种方法将 nums 分割为 2 个子数组。 
//其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
//因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,4,5], m = 2
//输出：9
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,4,4], m = 3
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 10⁶ 
// 1 <= m <= min(50, nums.length) 
// 
// Related Topics贪心 | 数组 | 二分查找 | 动态规划 
//
// 👍 707, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class SplitArrayLargestSum {
    public static void main(String[] args) {
        Solution solution = new SplitArrayLargestSum().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 和1011一致思路，需要类比一下
    class Solution {
        int f(int[] nums, int capacity) {
            int curCapacity = 0;
            int days = 0;
            for (int i = 0; i < nums.length; i++) {
                curCapacity += nums[i];

                if (curCapacity > capacity) {
                    days++;
                    curCapacity = nums[i];
                } else if (curCapacity == capacity) {
                    days++;
                    curCapacity = 0;
                }
            }

            if (curCapacity != 0) days++;

            return days;
        }

        public int splitArray(int[] nums, int m) {
            int left = 0, right = 1;
            for (int num : nums) {
                left = Math.max(left, num);
                right += num;
            }

            while (left < right) {
                int mid = left + (right - left) / 2;
                if (f(nums, mid) < m) {
                    right = mid;
                } else if (f(nums, mid) > m) {
                    left = mid + 1;
                } else if (f(nums, mid) == m) {
                    right = mid;
                }
            }

            return left;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
